/*
 *  Copyright 2012 Anton Van Zyl. http://code.google.com/p/java-swiss-knife/
 * 
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 * 
 *       http://www.apache.org/licenses/LICENSE-2.0
 * 
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 *  under the License.
 */
package com.knife.String;

import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * This is a implementation of some of the most common used algorithms in the
 * java world for strings. The algorithms was derived from Wiki into a usable
 * java language utility.
 * 
 * <br/>
 * <br/>
 * Please visit <a
 * href="http://code.google.com/p/java-swiss-knife/">Java-Swiss-Knife</a> and
 * comment, rate, contribute or raise a issue/enhancement for my library. <br/>
 * 
 * @author Anton Van Zyl
 * 
 */
public final class StringAlgorithmUtils {

	private static int minimum(int a, int b, int c) {
		return Math.min(Math.min(a, b), c);
	}

	/**
	 * The Levenshtein distance between two strings is defined as the minimum
	 * number of edits needed to transform one string into another.
	 * 
	 * @param str1
	 * @param str2
	 * @return The number of changes needed for strings to be equal
	 */
	public static int computeLevenshteinDistance(CharSequence str1, CharSequence str2) {
		int[][] distance = new int[str1.length() + 1][str2.length() + 1];

		for (int i = 0; i <= str1.length(); i++) {
			distance[i][0] = i;
		}

		for (int j = 0; j <= str2.length(); j++) {
			distance[0][j] = j;
		}

		for (int i = 1; i <= str1.length(); i++) {
			for (int j = 1; j <= str2.length(); j++) {
				distance[i][j] = minimum(distance[i - 1][j] + 1, distance[i][j - 1] + 1, distance[i - 1][j - 1] + ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1));
			}
		}
		return distance[str1.length()][str2.length()];
	}

	/**
	 * Dice's coefficient measures how similar a set and another set are. It can
	 * be used to measure how similar two strings are in terms of a number of
	 * common bigrams (A bigram is a pair of adjacent letters in the string.
	 * 
	 * @param s1
	 * @param s2
	 * @return similarity
	 */
	public static double diceCoefficient(String s1, String s2) {
		Set<String> nx = new HashSet<String>();
		Set<String> ny = new HashSet<String>();

		for (int i = 0; i < s1.length() - 1; i++) {
			char x1 = s1.charAt(i);
			char x2 = s1.charAt(i + 1);
			String tmp = "" + x1 + x2;
			nx.add(tmp);
		}

		for (int j = 0; j < s2.length() - 1; j++) {
			char y1 = s2.charAt(j);
			char y2 = s2.charAt(j + 1);
			String tmp = "" + y1 + y2;
			ny.add(tmp);
		}

		Set<String> intersection = new HashSet<String>(nx);
		intersection.retainAll(ny);
		double totcombigrams = intersection.size();
		return (2 * totcombigrams) / (nx.size() + ny.size());

	}

	/**
	 * The longest common subsequence (LCS) problem is to find the longest
	 * subsequence common to all sequences in a set of sequences (often just
	 * two).
	 * 
	 * @param s1
	 * @param s2
	 * @return List of common subsequence
	 */
	public static List<String> LongestCommonSubsequence(String[] s1, String[] s2) {
		int[][] num = new int[s1.length + 1][s2.length + 1]; // 2D array,
																// initialised
																// to 0

		// Actual algorithm from wiki
		for (int i = 1; i <= s1.length; i++) {
			for (int j = 1; j <= s2.length; j++) {
				if (s1[i - 1].equals(s2[j - 1])) {
					num[i][j] = 1 + num[i - 1][j - 1];
				} else {
					num[i][j] = Math.max(num[i - 1][j], num[i][j - 1]);
				}
			}
		}

		int s1position = s1.length, s2position = s2.length;
		List<String> result = new LinkedList<String>();

		while (s1position != 0 && s2position != 0) {
			if (s1[s1position - 1].equals(s2[s2position - 1])) {
				result.add(s1[s1position - 1]);
				s1position--;
				s2position--;
			} else if (num[s1position][s2position - 1] >= num[s1position - 1][s2position]) {
				s2position--;
			} else {
				s1position--;
			}
		}
		Collections.reverse(result);
		return result;
	}

}
